package com.demo.data.struct2.排序;

/**插入排序：把数组分为已排序和未排序两集合（初始时认为最左边第一个元素就是已排序集合的，其它属于未排序集合），
 * 从左边开始，第一轮拿出第1个元素，和第0个比，做排序；第二轮拿出第2个元素，和第0,1个元素比，做排序...
 * @author HP
 *
 */
public class InsertSort {

	public static int[] sort(int[] arr) {
		for(int i=1; i<arr.length; i++){
			int t = arr[i]; // t: 待插入的元素值
			int j = i-1; // j: 代表已排序区域的元素索引
			while(j>=0) {
				if(t < arr[j]){
					arr[j+1] = arr[j];
				}else {
					break; // 退出循环，减少比较次数
				}
				j--;
			}
			arr[j+1] = t; // 插入待插入元素
		}
		return arr;
	}

	public static void main(String[] args) {
		int[] arr = {9,3,1,4,2,7,8,6,5};
		Util.display(InsertSort.sort(arr));
	}

}
